This invention relates to an apparatus for converting a Gregory patch data in one system to a general patch data used for another system.
It is known that a Gregory patch proposed by Chiyokura and Kimura is an excellent representation which is capable of expressing a curved surface and interpolate a non-quadrilateral patch (See H. Chiyokura and F. Kimura, "Design of Solids with Free Form Surfaces", Computer Graphics (Proc. SIGGRAPH 83); Vol. 17, No. 3, July 1983, pp. 289-298). According to the Gregory patch, the complicated shape of the curved surface can be represented.
However, a method of transforming the Gregory patch data to the general patch data is not known, and a method which requires the division of a curved surface cannot apply to the Gregory patch. This is a problem in handling the Gergory patch (see E. Beeker "Smoothing of shapes designed with free-from surfaces" CAD, Vol. 18, No. 4, May 1986, pp. 224-232, or S. T. Tan and K. C. Chan "Generation of high order surfaces over arbitrary polyhedral meshes" CAD, Vol. 18, No. 8, October 1986; pp. 411-423).
The ray tracing is an algorithm to form a real image (see T. Whitted "An Improved Model for Shaded Display" Comm. ACM, Vol. 23, No. 6, June 1980, pp. 96-102) and there are developed several methods of ray tracing a free-form curved surface.
Generally, when a free-form curved surface is ray traced, the intersection of the surface and a ray of light must be calculated. To this end, there are a method which was performed by Toth using Newton's method (see D. L. Toth "On Ray Tracing Parametric Surfaces" Computer Graphics (Proc. SIGGRAPH 85), Vol. 19, No. 3, July 1985, pp. 171-179) and a method of calculating the intersection by implicitizing a free-form curved surface (see J. T. Kajiya "Ray Tracing Parametric Patches" Computer Graphics (Proc. SIGGRAPH 82), Vol. 16, No. 3, July 1982, pp. 245-254, or T. W. Sederberg and D. C. Anderson "ray Tracing of Steiner Patches" Computer Graphics (Proc. SIGGRAPH 84), Vol. 18, No. 3, July 1984, pp. 159-164. In order to calculate the intersection of the ray of light and the surface by Newton's method, the initial value toward which a solution by the Newton's method converges must be selected. To this end, Toth uses interval analysis.
The interval analysis is a method of analyzing whether a solution by the Newton's method converges when the equations for a curved surface and a ray of light are given and Newton's method is started from any point in an area in which the curved surface exists. If it is perceived that a solution by the Newton's method does not converge as a result of the interval analysis, the curved surface is divided to reduce the area in which the curved area exists and the convergence of a solution by the Newton's method according to the interval nanlysis is again examined.
When a Gregory patch is ray traced, implicitization of the Gregory patch brings about an at least 18th-degree equation to thereby increase the cost required for calculating the intersection, and any one of the previously mentioned related arts can not transform the Gregory patch data into general patch data such as rational Bezier patch data or a non-uniform rational B-Spline patch data.